{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Distinct Subsequences II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: distinctSubseqII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不同的子序列 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串 <code>s</code>，计算 <code>s</code> 的 <strong>不同非空子序列</strong> 的个数。因为结果可能很大，所以返回答案需要对<strong> </strong><strong><code>10^9 + 7</code> 取余</strong> 。</p>\n",
    "\n",
    "<p>字符串的 <strong>子序列</strong> 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"ace\"</code> 是 <code>\"<em><strong>a</strong></em>b<em><strong>c</strong></em>d<em><strong>e</strong></em>\"</code> 的一个子序列，但 <code>\"aec\"</code> 不是。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abc\"\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>7 个不同的子序列分别是 \"a\", \"b\", \"c\", \"ab\", \"ac\", \"bc\", 以及 \"abc\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aba\"\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>6 个不同的子序列分别是 \"a\", \"b\", \"ab\", \"ba\", \"aa\" 以及 \"aba\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aaa\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>3 个不同的子序列分别是 \"a\", \"aa\" 以及 \"aaa\"。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 2000</code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [distinct-subsequences-ii](https://leetcode.cn/problems/distinct-subsequences-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [distinct-subsequences-ii](https://leetcode.cn/problems/distinct-subsequences-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abc\"', '\"aba\"', '\"aaa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = [0] * 26\n",
    "        All = 1\n",
    "        for x in s:\n",
    "            c = ord(x) - ord('a')\n",
    "            newAdd = (All - cnt[c] + MOD) % MOD\n",
    "            cnt[c] = (newAdd + cnt[c]) % MOD\n",
    "            All = (All + newAdd) % MOD\n",
    "        return (All - 1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "f[i][j] 表示用 s 的前 i 个字符组成以 j 结尾的不同非空子序列的个数\n",
    "'''\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII1(self, s: str) -> int:\n",
    "        f = [[0] * 26 for _ in range(len(s) + 1)]\n",
    "        for i, c in enumerate(s, 1):\n",
    "            c = ord(c) - ord('a')\n",
    "            f[i] = f[i - 1].copy()\n",
    "            f[i][c] = (1 + sum(f[i - 1])) % MOD\n",
    "        return sum(f[-1]) % MOD\n",
    "        \n",
    "\n",
    "\n",
    "    '''\n",
    "    状态转移只发生在 i 和 i−1 之间，因此可以只用一个长为 26 的数组表示上述状态转移过程\n",
    "    除了 f[s[i]] 以外，其余值都不变，因此只需要更新 f[s[i]] 的值。\n",
    "    '''\n",
    "    def distinctSubseqII2(self, s: str) -> int:\n",
    "        f = [0] * 26\n",
    "        for c in s:\n",
    "            f[ord(c) - ord('a')] = (1 + sum(f)) % MOD\n",
    "        return sum(f) % MOD\n",
    "\n",
    "    '''\n",
    "    再优化，\n",
    "    '''\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        total = 0\n",
    "        f = [0] * 26\n",
    "        for c in s:\n",
    "            c = ord(c) - ord('a')\n",
    "            others = total - f[c]  # total 中不含 f[c] 的部分\n",
    "            f[c] = 1 + total  # 更新 f[c]\n",
    "            total = (f[c] + others) % MOD  # 更新 total\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [0] * 26\n",
    "        pres = 0\n",
    "        for ch in s:\n",
    "            cur = dp[ord(ch) - ord('a')]\n",
    "            dp[ord(ch) - ord('a')] = (pres + 1) % mod\n",
    "            pres += dp[ord(ch) - ord('a')] - cur\n",
    "        return sum(dp) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        total = 0\n",
    "        f = [0] * 26\n",
    "        for c in s:\n",
    "            c = ord(c) - ord('a')\n",
    "            others = total - f[c]  # total 中不含 f[c] 的部分\n",
    "            f[c] = 1 + total  # 更新 f[c]\n",
    "            total = (f[c] + others) % MOD  # 更新 total\n",
    "        return total\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/distinct-subsequences-ii/solutions/1890716/xi-fen-wen-ti-fu-za-du-you-hua-pythonjav-1ihu/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        dp = [0] * 26\n",
    "        for c in s:\n",
    "            i = ord(c) - ord('a')\n",
    "            dp[i] = sum(dp) % mod + 1\n",
    "        return sum(dp) % mod\n",
    "\n",
    "# 作者：ylb\n",
    "# 链接：https://leetcode.cn/problems/distinct-subsequences-ii/solutions/1890745/by-lcbin-beio/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        char_count = {}\n",
    "        total = 1\n",
    "\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            char = s[i]\n",
    "            num = char_count.get(char, 0)\n",
    "            add = total - num\n",
    "            total += add\n",
    "            char_count[char] = num + add\n",
    "\n",
    "        return (total - 1) % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 1000000007\n",
    "        cnt = [0]*26\n",
    "        all = 1\n",
    "        newAdd = 0\n",
    "        for x in s:\n",
    "            newAdd = (all-cnt[ord(x)-ord('a')]+mod)%mod\n",
    "            cnt[ord(x)-ord('a')] = (cnt[ord(x)-ord('a')]+newAdd)%mod\n",
    "            all = (all+newAdd)%mod\n",
    "        return (all-1+mod)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod=10**9+7\n",
    "        d=defaultdict(int)\n",
    "        n=len(s)\n",
    "        cur=1\n",
    "        for i in range(0,n):\n",
    "            pre=cur\n",
    "            cur=((cur+pre)%mod-d[s[i]]+mod)%mod\n",
    "            d[s[i]]=pre\n",
    "        return (cur-1+mod)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        if s == None: return 0\n",
    "        all, newAdd = 1, 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        chars = [0] * 26 # 以a、b、c... 结尾的子序列，有几个\n",
    "        for x in s:\n",
    "            j = ord(x) - ord('a')\n",
    "            newAdd = (all -  chars[j]) % MOD\n",
    "            chars[j] = (newAdd +chars[j]) % MOD\n",
    "            all = (newAdd + all) % MOD\n",
    "        return (all - 1 + MOD) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        g = [0] * 26\n",
    "        total = 0\n",
    "        for c in s:\n",
    "            i = ord(c) - 97\n",
    "            g[i], total = (total + 1) % MOD, (total * 2 + 1 - g[i]) % MOD\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        f = [0] * 26\n",
    "        for i, letter in enumerate(s):\n",
    "            tmp = (1 + sum(f)) % mod\n",
    "            f[ord(letter) - ord('a')] = tmp\n",
    "        return sum(f) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        pre = [0]*26\n",
    "        for w in s:\n",
    "            s = sum(pre) % mod\n",
    "            i = ord(w) - ord(\"a\")\n",
    "            pre[i] = s + 1\n",
    "            pre[i] %= mod\n",
    "        return sum(pre) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        count = {}\n",
    "        total = 1\n",
    "\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            char = s[i]\n",
    "            num = count.get(char, 0)\n",
    "            add = total - num\n",
    "            total += add\n",
    "            count[char] = num + add\n",
    "\n",
    "        return (total - 1) % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        # 所有由前i个字母的组成且结尾为j的所有不同方案的数量。\n",
    "        # 当ai不等于j 则f[i][j] = f[i - 1][j] \n",
    "        # 当ai等于j 枚举第i-1个字母是k，k可以取到26个字母和空， 那么前i-1个字母且结尾是k的方案数量是f[i - 1][k]\n",
    "        f = defaultdict(int)\n",
    "        for ch in s:\n",
    "            x = ord(ch) - 97\n",
    "            t = 1\n",
    "            for i in range(26):\n",
    "                t = (t + f[i]) % MOD\n",
    "            f[x] = t\n",
    "        res = 0\n",
    "        for k, v in f.items():\n",
    "            res += v\n",
    "            res %= MOD\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = [0] * 26\n",
    "        All = 1\n",
    "        for x in s:\n",
    "            c = ord(x) - ord('a')\n",
    "            newAdd = All - cnt[c]\n",
    "            cnt[c] = newAdd + cnt[c]\n",
    "            All = (All + newAdd) % MOD\n",
    "        return (All - 1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10**9+7\n",
    "        n = len(s)\n",
    "        dp = [0] * n\n",
    "        dp[0] = 1\n",
    "        precount = dict()\n",
    "        precount[s[0]] = 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            c = s[i]\n",
    "            newcount = dp[i-1] + 1\n",
    "            repeatcount = precount[c] if c in precount else 0\n",
    "            dp[i] = (dp[i-1] + newcount - repeatcount) % mod\n",
    "            precount[c] = newcount\n",
    "        \n",
    "        # print(dp)\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = defaultdict(int)\n",
    "        for ch in s:\n",
    "            x = ord(ch) - 97\n",
    "            t = 1\n",
    "            for i in range(26):\n",
    "                t = (t + f[i]) % MOD\n",
    "            f[x] = t\n",
    "        res = 0\n",
    "        for v in f.values():\n",
    "            res += v\n",
    "            res %= MOD\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod=10**9+7\n",
    "        d=defaultdict(int)\n",
    "        n=len(s)\n",
    "        cur=1\n",
    "        for i in range(0,n):\n",
    "            pre=cur\n",
    "            cur=((cur+pre)%mod-d[s[i]]+mod)%mod\n",
    "            d[s[i]]=pre\n",
    "        return (cur-1+mod)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "md = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        last = [-1] * 26\n",
    "\n",
    "        f = [1] * n\n",
    "\n",
    "        for i, ch in enumerate(s):\n",
    "            for j in range(26):\n",
    "                if last[j] != -1:\n",
    "                    f[i] = (f[i] + f[last[j]]) % md\n",
    "            last[ord(ch) - ord('a')] = i\n",
    "        # print(f)\n",
    "        res = 0\n",
    "        for i in range(26):\n",
    "            if last[i] != -1:\n",
    "                res = (res + f[last[i]]) % md\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        思路：从左往右遍历，all表示 i位置以前，有多少子序列。\n",
    "            chars数组，表示 以某个字符 结尾的子序列，有多少个。因为后续出翔相同字符时，\n",
    "            会因此产生重复的子序列。\n",
    "        具体，就是需要推导一遍，就能理解了\n",
    "    '''\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        if s == None: return 0\n",
    "        all, newAdd = 1, 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        chars = [0] * 26 # 以a、b、c... 结尾的子序列，有几个\n",
    "        for x in s:\n",
    "            j = ord(x) - ord('a')\n",
    "            newAdd = (all -  chars[j]) % MOD\n",
    "            chars[j] = (newAdd +chars[j]) % MOD\n",
    "            all = (newAdd + all) % MOD\n",
    "        return (all - 1 + MOD) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        map = {}\n",
    "        all = 1\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            char = s[i]\n",
    "            num = map.get(char,0)\n",
    "            add = all - num\n",
    "            all += add\n",
    "            map[char] = num + add\n",
    "        return (all - 1) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        f,g,mod=1,[0]*26,1000000007\n",
    "        for i in range(0,len(s)):\n",
    "            f,g[ord(s[i])-97]=(2*f-g[ord(s[i])-97]+mod)%mod,f\n",
    "        return (f-1+mod)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        last = [-1] * 26\n",
    "        \n",
    "        n = len(s)\n",
    "        dp = [1] * n\n",
    "        for i, char in enumerate(s):\n",
    "            for j in range(26):\n",
    "                if last[j] != -1:\n",
    "                    dp[i] = (dp[i] + dp[last[j]]) % mod\n",
    "            last[ord(s[i]) - ord('a')] = i\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(26):\n",
    "            if last[i] != -1:\n",
    "                ans = (ans + dp[last[i]]) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [0] * 26\n",
    "        tot = 0\n",
    "        for i in range(len(s)):\n",
    "            ci = ord(s[i]) - ord('a')\n",
    "            u = tot + 1 - dp[ci]\n",
    "            dp[ci] = (tot + 1) % mod\n",
    "            tot = (tot + u + mod) % mod\n",
    "        return tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        arrays = [-1] * 26\n",
    "        dp = [1] * n\n",
    "        for i in range(n):\n",
    "            for j in range(26):\n",
    "                if arrays[j] != -1:\n",
    "                    dp[i] = (dp[i] + dp[arrays[j]]) % mod\n",
    "\n",
    "            arrays[ord(s[i]) - ord('a')] = i\n",
    "\n",
    "        res = 0\n",
    "        for i in range(26):\n",
    "            if arrays[i] != -1:\n",
    "                res = (res + dp[arrays[i]]) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        arrays = [-1] * 26\n",
    "        dp = [0] * n\n",
    "        for i in range(n):\n",
    "            base = 1\n",
    "            for j in range(26):\n",
    "                if arrays[j] != -1:\n",
    "                    base = (base + dp[arrays[j]]) % mod\n",
    "\n",
    "            arrays[ord(s[i]) - ord('a')] = i\n",
    "            dp[i] = base\n",
    "\n",
    "        res = 0\n",
    "        for i in range(26):\n",
    "            if arrays[i] != -1:\n",
    "                res = (res + dp[arrays[i]]) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0]*26\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(26):\n",
    "                cnt += dp[j]\n",
    "            c = ord(s[i]) - ord('a')\n",
    "            dp[c] = cnt + 1\n",
    "        ans = 0\n",
    "        for x in dp:\n",
    "            ans = (ans+x)%(10**9+7)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        # f[i][j] 表示用s的前i个字符组成以j结尾的不同非空子序列的个数\n",
    "        # if s[i-1] != j:f[i][j] = f[i-1][j]\n",
    "        # s[i-1] == j:f[i][j] =sum(f[i][j‘])+1 \n",
    "        f = [0]*26\n",
    "        total = 0\n",
    "        for c in s:\n",
    "            c = ord(c)-ord('a')\n",
    "            others = total - f[c]\n",
    "            f[c] = 1 + total\n",
    "            total = (f[c] + others)\n",
    "        return total%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        arrays = [-1] * 26\n",
    "        dp = [0] * n\n",
    "        for i in range(n):\n",
    "            base = 1\n",
    "            for j in range(26):\n",
    "                if arrays[j] != -1:\n",
    "                    base = (base + dp[arrays[j]]) % mod\n",
    "\n",
    "            arrays[ord(s[i]) - ord('a')] = i\n",
    "            dp[i] = base\n",
    "\n",
    "        res = 0\n",
    "        for i in range(26):\n",
    "            if arrays[i] != -1:\n",
    "                res = (res + dp[arrays[i]]) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        # 不同非空子序列，选or不选\n",
    "        # 从左往右遍历 \n",
    "        # 当前字符加入之前所有子序列的末尾+单独的当前字符\n",
    "        f = [0] * 26 \n",
    "        for i, c in enumerate(s, 1):\n",
    "            c = ord(c) - ord('a')\n",
    "            f[c] = (1 + sum(f)) % MOD\n",
    "        return sum(f) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        last = [-1] * 26\n",
    "\n",
    "        n = len(s)\n",
    "        f = [1] * n\n",
    "        for i, ch in enumerate(s):\n",
    "            for j in range(26):\n",
    "                if last[j] != -1:\n",
    "                    f[i] = (f[i] + f[last[j]]) % mod\n",
    "            last[ord(s[i]) - ord(\"a\")] = i\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(26):\n",
    "            if last[i] != -1:\n",
    "                ans = (ans + f[last[i]]) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [0] * 26\n",
    "        for ch in s:\n",
    "            dp[ord(ch) - ord('a')] = sum(dp) + 1\n",
    "        \n",
    "        return sum(dp) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        state = [0] * 26\n",
    "        presum = 0\n",
    "        for si in s:\n",
    "            prei = state[ord(si) - ord(\"a\")]\n",
    "            state[ord(si) - ord(\"a\")] = presum + 1\n",
    "            presum += presum + 1 - prei\n",
    "        return presum % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [0] * 26\n",
    "        for c in s:\n",
    "            i = ord(c) - ord('a')\n",
    "            dp[i] = sum(dp) % mod + 1\n",
    "        return sum(dp) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        dp = [0] * 26\n",
    "        for c in s:\n",
    "            i = ord(c) - ord('a')\n",
    "            dp[i] = sum(dp) % mod + 1\n",
    "        return sum(dp) % mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        dp = [0] * n\n",
    "        last = [-1] * 26\n",
    "        for i, c in enumerate(s):        \n",
    "            dp[i] = 1\n",
    "            for j in range(26):\n",
    "                if last[j] != -1:\n",
    "                    dp[i] += dp[last[j]] \n",
    "                    dp[i] %= MOD  \n",
    "            last[ord(c) - ord('a')] = i \n",
    "        return sum(dp[last[i]] for i in range(26) if last[i] != -1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        f = [0] * 26\n",
    "        for c in s:\n",
    "            f[ord(c) - ord('a')] = (1 + sum(f)) % MOD\n",
    "        return sum(f) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        tag = {}\n",
    "        dp = [0 for _ in range(n)]\n",
    "        for k, i in enumerate(s):\n",
    "            if k == 0:\n",
    "                dp[k] = 1\n",
    "                tag[i] = 1\n",
    "            else:\n",
    "                if i not in tag:\n",
    "                    dp[k] = 2 * dp[k - 1] + 1\n",
    "                    tag[i] = dp[k] - dp[k - 1]\n",
    "                else:\n",
    "                    dp[k] = 2 * dp[k - 1] + 1 - tag[i]\n",
    "                    tag[i] += dp[k] - dp[k - 1]\n",
    "        return dp[-1] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        state = [0] * 26\n",
    "        sall = 0\n",
    "        for i, v in enumerate(s):\n",
    "            pre = state[ord(v) - ord(\"a\")]\n",
    "            state[ord(v) - ord(\"a\")] = sall + 1\n",
    "            sall += state[ord(v) - ord(\"a\")] - pre\n",
    "        return sall % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        total = 0\n",
    "        f = [0] * 26\n",
    "        for c in s:\n",
    "            c = ord(c) - ord('a')\n",
    "            others = total - f[c]  # total 中不含 f[c] 的部分\n",
    "            f[c] = 1 + total  # 更新 f[c]\n",
    "            total = (f[c] + others) % MOD  # 更新 total\n",
    "        return total\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10**9 + 7  # 定义取模值，用于最终结果的取模运算\n",
    "\n",
    "        # 初始化一个长度为 26 的数组，用于存储每个小写字母在字符串 s 中最后出现的位置\n",
    "        last = [-1] * 26\n",
    "\n",
    "        n = len(s)  # 获取字符串 s 的长度\n",
    "        f = [1] * n  # 初始化一个长度为 n 的数组，用于存储以每个字符结尾的不同子序列数量，初始值都为 1\n",
    "\n",
    "        # 遍历字符串 s 中的每个字符及其索引\n",
    "        for i, ch in enumerate(s):\n",
    "            # 遍历字母表中的每个字母（a-z）\n",
    "            for j in range(26):\n",
    "                if last[j] != -1:\n",
    "                    # 如果字母 j 在字符串 s 中之前出现过\n",
    "                    # 则将以当前字符结尾的不同子序列数量加上以字母 j 结尾的不同子序列数量\n",
    "                    f[i] = (f[i] + f[last[j]]) % mod\n",
    "            # 更新字母 ch 的最后出现位置为当前索引 i\n",
    "            last[ord(ch) - ord(\"a\")] = i\n",
    "        \n",
    "        ans = 0  # 初始化最终答案为 0\n",
    "        # 遍历字母表中的每个字母（a-z）\n",
    "        for i in range(26):\n",
    "            if last[i] != -1:\n",
    "                # 如果字母 i 在字符串 s 中出现过\n",
    "                # 则将以字母 i 结尾的不同子序列数量累加到最终答案中\n",
    "                ans = (ans + f[last[i]]) % mod\n",
    "        return ans  # 返回最终答案\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        dp = [0] * 26  #创建一个元素均为0的数组\n",
    "        for c in s: #遍历字符串\n",
    "            i = ord(c) - ord('a') #uniclde编码确定对应字符的位置\n",
    "            dp[i] = sum(dp) % mod + 1 #计算出所有不同子序列的个数，+1是指i对应字符串本身也可以作为一个子序列。\n",
    "        return sum(dp) % mod #对dp中的所有元素求和，再取余\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 1000000007\n",
    "        n = len(s)\n",
    "        dp = [0]*26\n",
    "        all = 1\n",
    "        for i in range(n):\n",
    "            newadd = all-dp[ord(s[i])-ord('a')]\n",
    "            dp[ord(s[i])-ord('a')] += newadd\n",
    "            all += newadd\n",
    "        return sum(dp)%mod "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod=10**9+7\n",
    "        last=[-1]*26\n",
    "\n",
    "        n=len(s)\n",
    "        f=[1]*n\n",
    "        for i,ch in enumerate(s):\n",
    "            for j in range(26):\n",
    "                if last[j]!=-1:\n",
    "                    f[i]=(f[i]+f[last[j]])%mod\n",
    "            last[ord(s[i])-ord(\"a\")]=i\n",
    "\n",
    "        ans=0\n",
    "        for i in range(26):\n",
    "            if last[i]!=-1:\n",
    "                ans=(ans+f[last[i]])%mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        # f[i][j] 表示用s的前i个字符组成以j结尾的不同非空子序列的个数\n",
    "        # if s[i-1] != j:f[i][j] = f[i-1][j]\n",
    "        # s[i-1] == j:f[i][j] =sum(f[i][j‘])+1 \n",
    "        f = [0]*26\n",
    "        for c in s:\n",
    "            f[ord(c)-ord('a')] = sum(f) + 1\n",
    "        return sum(f)%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        last = [-1] * 26\n",
    "        n = len(s)\n",
    "        res = [1] * n\n",
    "        for i, l in enumerate(s):\n",
    "            for j in range(26):\n",
    "                if last[j] != -1:\n",
    "                    res[i] = (res[i] + res[last[j]]) % mod\n",
    "            last[ord(l) - ord('a')] = i\n",
    "        ans = 0\n",
    "        for i in range(26):\n",
    "            if last[i] != -1:\n",
    "                ans = (ans + res[last[i]]) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        arr = [0] * 26\n",
    "        for c in s:\n",
    "            arr[ord(c)-ord('a')] = 1 + sum(arr)\n",
    "        return sum(arr) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod=10**9+7\n",
    "        dp=[1]\n",
    "        dic={}\n",
    "        for i,c in enumerate(s):\n",
    "            dp.append(dp[i]*2)\n",
    "            if c in dic:\n",
    "                dp[-1]-=dp[dic[c]]\n",
    "            dic[c]=i\n",
    "        return (dp[-1]-1)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        last = [-1] * 26\n",
    "        n = len(s)\n",
    "        res = [1] * n\n",
    "        for i, l in enumerate(s):\n",
    "            for j in range(26):\n",
    "                if last[j] != -1:\n",
    "                    res[i] = (res[i] + res[last[j]]) % mod\n",
    "            last[ord(l) - ord('a')] = i\n",
    "        ans = 0\n",
    "        for i in range(26):\n",
    "            if last[i] != -1:\n",
    "                ans += res[last[i]]\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        last = [-1] * 26\n",
    "\n",
    "        n = len(s)\n",
    "        f = [1] * n\n",
    "        for i, ch in enumerate(s):\n",
    "            for j in range(26):\n",
    "                if last[j] != -1:\n",
    "                    f[i] = (f[i] + f[last[j]]) % mod\n",
    "            last[ord(s[i]) - ord(\"a\")] = i\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(26):\n",
    "            if last[i] != -1:\n",
    "                ans = (ans + f[last[i]]) % mod\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        last = [-1, ] * 26  # 字母最后出现位置\n",
    "        dp = [1, ] * len(s)\n",
    "        for i in range(len(s)):\n",
    "            for j in range(26):\n",
    "                if last[j] != -1:\n",
    "                    dp[i] += dp[last[j]]\n",
    "            last[ord(s[i])-ord(\"a\")] = i\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(26):\n",
    "            if last[i] != -1:\n",
    "                ans += dp[last[i]]\n",
    "        return ans % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        # 对于子序列问题，通常可以从每个元素选或者不选的角度入手\n",
    "        # 麻烦的地方在于，如何保证对于同样的子序列，我们只统计一次？\n",
    "        # 分别统计以 'a', 'b', ... 'z'结尾的不同子序列的个数\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        f = [[0] * 26 for _ in range(n + 1)]\n",
    "        for i, x in enumerate(s):\n",
    "            for j in range(26):\n",
    "                if ord(x) - ord('a') == j:\n",
    "                    f[i + 1][j] = 1 + sum(f[i][k] for k in range(26)) % mod\n",
    "                else:\n",
    "                    f[i + 1][j] = f[i][j]\n",
    "        return sum(f[-1]) % mod\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        n = len(s)\n",
    "        f = [[0]*26 for _ in range(n + 1)]\n",
    "\n",
    "        for i in range(1,n + 1):\n",
    "            t = ord(s[i - 1]) - ord('a')\n",
    "            for j in range(26):\n",
    "                if j != t:\n",
    "                    f[i][j] = f[i - 1][j]\n",
    "                else:\n",
    "                    f[i][t] += 1 + sum(f[i - 1])\n",
    "                    f[i][t] %= MOD\n",
    "        return sum(f[-1]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        # 不同非空子序列，选or不选\n",
    "        # 从左往右遍历 \n",
    "        # 当前字符加入之前所有子序列的末尾+单独的当前字符\n",
    "        f = [[0] * 26 for _ in range(len(s) + 1)]\n",
    "        for i, c in enumerate(s, 1):\n",
    "            c = ord(c) - ord('a')\n",
    "            f[i] = f[i - 1].copy()\n",
    "            f[i][c] = (1 + sum(f[i - 1])) % MOD\n",
    "        return sum(f[-1]) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        # dp[i] 表示前i个字符可以组成的不同子序列\n",
    "        # dp[i] = dp[i-1] + 新增的 -重复的\n",
    "\n",
    "        # https://leetcode.cn/problems/distinct-subsequences-ii/solutions/1890717/bu-tong-by-capital-worker-vga3/\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        dp = [0] * (n + 1) \n",
    "        dp[0] = 1 #空字符串\n",
    "\n",
    "        last = [0] * 26 \n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            dp[i] = dp[i-1] + dp[i-1] - last[ord(s[i-1]) - ord('a')]\n",
    "\n",
    "            # 最后一次出现该字符新增的个数\n",
    "            last[ord(s[i-1]) - ord('a')] += dp[i] - dp[i-1]\n",
    "\n",
    "\n",
    "        return (dp[-1] - 1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        f = [[0] * 26 for _ in range(len(s) + 1)]\n",
    "        for i, c in enumerate(s, 1):\n",
    "            c = ord(c) - ord('a')\n",
    "            f[i] = f[i - 1].copy()\n",
    "            f[i][c] = (1 + sum(f[i - 1])) % MOD\n",
    "        return sum(f[-1]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 1000000007\n",
    "        dp = [1] + [0] * len(s)\n",
    "        cnt = [0] * 26\n",
    "        for i in range(1, len(s)+1):\n",
    "            newCnt = dp[i-1]\n",
    "            repeat = cnt[ord(s[i-1]) - ord('a')]\n",
    "            dp[i] = dp[i-1] + newCnt - repeat\n",
    "            cnt[ord(s[i-1]) - ord('a')] = newCnt\n",
    "        print(dp)\n",
    "        return (dp[-1]-1)%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        f=[[0]*26 for _ in range(n+1)]\n",
    "        mod=10**9+7\n",
    "        for i,c in enumerate(s,1):\n",
    "            c=ord(c)-ord('a')\n",
    "            f[i]=f[i-1].copy()\n",
    "            f[i][c]=(1+sum(f[i-1]))%mod\n",
    "        return sum(f[-1])%mod\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        f = [[0] * 26 for _ in range(len(s) + 1)]\n",
    "        for i, c in enumerate(s, 1):\n",
    "            c = ord(c) - ord('a')\n",
    "            f[i] = f[i - 1].copy()\n",
    "            f[i][c] = 1 + sum(f[i - 1]) % mod\n",
    "        return sum(f[-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * 26 for _ in range(n + 1)]\n",
    "\n",
    "        for i, ch in enumerate(s, 1):\n",
    "            dp[i] = dp[i - 1][::]\n",
    "            dp[i][ord(ch) - ord('a')] = (1 + sum(dp[i - 1])) % kmod\n",
    "        \n",
    "        return sum(dp[-1]) % kmod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0]*26 for _ in range(n+1)]\n",
    "        mod = 10**9+7\n",
    "        pre = 0\n",
    "        cur = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(26):\n",
    "                if ord(s[i-1])-97 != j:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = 1 + pre\n",
    "                cur += dp[i][j]\n",
    "            pre = cur\n",
    "            cur = 0\n",
    "            \n",
    "        res = 0\n",
    "        for i in range(26):\n",
    "            res = (res + dp[n][i])%mod\n",
    "        return res\n",
    "\n",
    "        \n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        mod = 10**9+7\n",
    "        # f[i][j]为0-i-1以j 结尾的不同非空子序列的个数,j为'a','b','c',...\n",
    "        n = len(s)\n",
    "        f = [[0]*26 for _ in range(n+1)]\n",
    "        for i,c in enumerate(s,1):\n",
    "            c = ord(c) - ord('a')\n",
    "            f[i] = f[i-1].copy()\n",
    "            f[i][c] = (1 + sum(f[i-1]))%mod\n",
    "        return sum(f[-1])%mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        # 对于子序列问题，通常可以从每个元素选或者不选的角度入手\n",
    "        # 麻烦的地方在于，如何保证对于同样的子序列，我们只统计一次？\n",
    "        # 分别统计以 'a', 'b', ... 'z'结尾的不同子序列的个数\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        f = [[0] * 26 for _ in range(n + 1)]\n",
    "        for i, x in enumerate(s):\n",
    "            for j in range(26):\n",
    "                if ord(x) - ord('a') == j:\n",
    "                    f[i + 1][j] = 1 + sum(f[i][k] for k in range(26))\n",
    "                else:\n",
    "                    f[i + 1][j] = f[i][j]\n",
    "        return sum(f[-1]) % mod\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0]*26 for _ in range(n+1)]\n",
    "        mod = 10**9+7\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(26):\n",
    "                if ord(s[i-1])-97 != j:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = 1 + sum(dp[i-1])\n",
    "        res = 0\n",
    "        for i in range(26):\n",
    "            res = (res + dp[n][i])%mod\n",
    "        return res\n",
    "\n",
    "        \n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        f = [[0] * 26 for _ in range(len(s) + 1)]\n",
    "        for i, c in enumerate(s, 1):\n",
    "            c = ord(c) - ord('a')\n",
    "            f[i] = f[i - 1].copy()\n",
    "            f[i][c] = (1 + sum(f[i - 1])) % MOD\n",
    "        return sum(f[-1]) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0]*26 for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(26):\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                cnt += dp[i-1][j]\n",
    "            c = ord(s[i]) - ord('a')\n",
    "            dp[i][c] = cnt + 1\n",
    "        ans = 0\n",
    "        for x in dp[n-1]:\n",
    "            ans = (ans+x)%(10**9+7)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSubseqII(self, s: str) -> int:\n",
    "        n, mod = len(s), 10**9+7\n",
    "        dp = [[0]*26 for _ in range(n+1)]\n",
    "        pre, cur = 0, 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(26):\n",
    "                if ord(s[i-1])-97 != j:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = 1 + pre\n",
    "                cur += dp[i][j]\n",
    "            pre,cur = cur, 0   \n",
    "        res = 0\n",
    "        for i in range(26):\n",
    "            res = (res + dp[n][i])%mod\n",
    "        return res\n",
    "\n",
    "        \n",
    "                    \n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
